Sliding Window

121 Best Time to Buy and Sell Stock

def maxProfit(prices: List[int]) -> int:
  res = 0
  lowest = prices[0]
  for i in range(len(prices)):
    if prices[i] < lowest:
      lowest = prices[i]
    else:
      res = max(res, prices[i] - lowest)
  return res

3 Longest Substring Without Repeating Characters

Time Complexity: O(n). The sliding window technic only require us to iterate over the input string once.

Space Complexity: O(1). The memo hash set can only contain unique characters, at most 26 characters which is O(1).

def lengthOfLongestSubstring(s: str) -> int:
  memo = set()
  l, r = 0, 0
  res = 0

  while r < len(s):
    if s[r] not in memo:
      memo.add(s[r])
      r += 1
      res = max(res, r - l)
    else:
      memo.remove(s[l])
      l += 1
 
  return res

424 Longest Repeating Character Replacement